Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

O( n^2 ) time O(1) space solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        int start = 0, maxLength = 1;
        
        for (int i = 0; i < s.length();){
            if (s.length() - i <= maxLength / 2) break;
            int j = i, k = i;
            
            // skip duplicates
            while (k < s.length() - 1 && s.charAt(k + 1) == s.charAt(k)){k++;} 
            // reset i
            i = k + 1;
            // expand
            while (k < s.length() - 1 && j > 0 && s.charAt(k + 1) == s.charAt(j - 1)){
                k++;
                j--;
            }
            
            if (maxLength < k - j + 1){
                start = j;
                maxLength = k - j + 1;
            }
        }
        
        return s.substring(start, start + maxLength);
    }
}

O( n ^2 ) time O( n^2 ) space DP solution, can be optimized to O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null) return s;
        int start = 0, length = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
        
        for (int left = s.length() - 1; left >= 0; left--) {
            for (int right = left; right < s.length(); right++) {
                dp[left][right] = s.charAt(left) == s.charAt(right) && (right - left < 3 || dp[left + 1][right - 1]);
                
                if (dp[left][right] && right - left + 1 > length) {
                    start = left;
                    length = right - left + 1;
                }
            }
        }
        return s.substring(start, start + length);
    }
}

O(n) time Manacher’s Algorithm

https://www.felix021.com/blog/read.php?2040